def binary_search(nums, target):
    """二分查找"""
    left = 0
    right = len(nums)
    while left < right:
        mid = (left + right) // 2
        if target == nums[mid]:
            return True
        elif target < nums[mid]:
            right = mid
        else:
            left = mid + 1
    return False


def binary_search_dg(nums, target):
    """二分查找（递归）"""
    if len(nums) == 0:
        return False
    mid = len(nums) // 2
    if target == nums[mid]:
        return True
    elif target < nums[mid]:
        return binary_search_dg(nums[: mid], target)
    else:
        return binary_search_dg(nums[mid+1:], target)


if __name__ == '__main__':
    print(list(range(1, 8)))
    print(binary_search_dg(list(range(1, 8)), 5))
